package pers.qianyu.month_202012.date_20201212;

import org.junit.*;

import java.util.*;

/**
 * [同 date_20201202]
 * 316. 去除重复字母
 * https://leetcode-cn.com/problems/remove-duplicate-letters/
 *
 * @author mizzle rain
 * @date 2020-12-12 17:45
 */
public class RemoveDuplicateLetters {
    public String removeDuplicateLetters(String s) {
        int[] dict = new int[26];
        for (int i = 0; i < s.length(); i++) {
            dict[s.charAt(i) - 'a']++;
        }
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (st.contains(ch)) {
                dict[ch - 'a']--;
                continue;
            }
            while (!st.isEmpty() && dict[st.peek() - 'a'] > 1 && st.peek() > ch) {
                dict[st.pop() - 'a']--;
            }
            st.push(ch);
            //System.out.println(st);
        }
        StringBuilder builder = new StringBuilder();
        for (Character ch : st) {
            builder.append(ch);
        }
        return builder.toString();
    }

    @Test
    public void test1() {
        String result = new RemoveDuplicateLetters()
                .removeDuplicateLetters("cbacdcbc");
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        String result = new RemoveDuplicateLetters()
                .removeDuplicateLetters("bbcaac");
        System.out.println("result = " + result);
    }

    @Test
    public void test3() {
        String result = new RemoveDuplicateLetters()
                .removeDuplicateLetters("abacb");
        System.out.println("result = " + result);
    }
}
